package 中等.模拟;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 堆盘子。设想有一堆盘子，堆太高可能会倒下来。因此，在现实生活中，盘
 * 子堆到一定高度时，我们就会另外堆一堆盘子。请实现数据结构SetOfStacks，
 * 模拟这种行为。SetOfStacks应该由多个栈组成，并且在前一个栈填满时新
 * 建一个栈。此外，SetOfStacks.push()和SetOfStacks.pop()应该与普通
 * 栈的操作方法相同（也就是说，pop()返回的值，应该跟只有一个栈时的情
 * 况一样）。 进阶：实现一个popAt(int index)方法，根据指定的子栈，执行pop操作。
 * <p>
 * 当某个栈为空时，应当删除该栈。当栈中没有元素或不存在该栈时，pop，popAt 应返回 -1.
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/stack-of-plates-lcci
 */
public class 堆盘子_0303 {

    public static void main(String[] args) {

        //["StackOfPlates", "push", "push", "popAt", "pop", "pop"]
        //[[1], [1], [2], [1], [], []]
        StackOfPlates stackOfPlates = new StackOfPlates(2);
        stackOfPlates.push(1);
        stackOfPlates.push(2);
        stackOfPlates.push(3);
        System.out.println(stackOfPlates.popAt(0));
        System.out.println(stackOfPlates.popAt(0));
        System.out.println(stackOfPlates.popAt(0));

    }

    /**
     * 数组+栈模拟
     */
    static class StackOfPlates {

        private List<Deque<Integer>> list = new ArrayList<>();

        private int maxSize;

        public StackOfPlates(int cap) {
            maxSize = cap;
        }

        public void push(int val) {
            if (maxSize == 0) return;
            if (list.size() == 0) {
                list.add(new ArrayDeque<>());
            }
            Deque<Integer> stack = list.get(list.size() - 1);
            if (stack.size() == maxSize) {
                list.add(new ArrayDeque<>());
                stack = list.get(list.size() - 1);
            }
            stack.addFirst(val);
        }

        public int pop() {
            if (list.size() == 0) {
                return -1;
            }
            Deque<Integer> stack = list.get(list.size() - 1);
            Integer val = stack.pollFirst();

            if (stack.isEmpty()) {
                list.remove(list.size() - 1);
            }
            return val;
        }

        public int popAt(int index) {
            if (index >= 0 && index < list.size()) {
                Deque<Integer> stack = list.get(index);
                Integer val = stack.pollFirst();
                if (stack.isEmpty()) {
                    list.remove(index);
                }
                return val;
            }
            return -1;
        }
    }

}
